package com.duing.recu;

import java.util.Arrays;

public class Fibonacci {

    public static void main(String[] args) {
        //fib(6);
        //fib1(6);
        fib2(6);
    }

    public static int fib(int N) {
        if (N == 1) return 1;
        if (N == 2) return 1;
        System.out.println("求第" + N + "个月的兔子数量");
        System.out.println("转化为求第" + (N - 1) + "个月和第" + (N - 2) + "个月的兔子数量");
        return fib(N - 1) + fib(N - 2);
    }


    // 记忆化递归
    // 使用数组  存储中间环节的值 （避免重复计算）
    public static int fib1(int N) {
        int[] arr = new int[N + 1];

        int result = fib1ByRecu(N, arr);
        System.out.println(Arrays.toString(arr));
        return result;
    }

    public static int fib1ByRecu(int N, int[] arr) {
        System.out.println("求第" + N + "个月的兔子数量,Array:" + Arrays.toString(arr));
        if (arr[N] != 0) {
            System.out.println(N + "的值已求取过，直接返回" + arr[N]);
            return arr[N];
        }

        if (N == 1) {
            arr[N] = 1;
            return 1;
        }
        if (N == 2) {
            arr[N] = 1;
            return 1;
        }

        int result = fib1ByRecu(N - 1, arr) + fib1ByRecu(N - 2, arr);
        arr[N] = result;
        System.out.println(N + "的值第一次求取，存储为" + arr[N]);
        return result;
    }

    // 动态规划
    // 直接给数组赋值
    public static int fib2(int N) {
        if (N == 1) return 1;
        if (N == 2) return 1;

        int[] arr = new int[N + 1];
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i < N + 1; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        System.out.println(Arrays.toString(arr));
        return arr[N];
    }

}
